package com.example.sort;

/**
 * Created by Quincy on 2018/9/11.
 * 冒泡排序
 */
public class BubbleSort {

    private BubbleSort(){}

    /**
     * 常规排序
     * */
    public static void sort1(Comparable[] arr){

        int n = arr.length;
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n-i; j++){   // 这里之所以要减去i，因为第一次遍历，最后一个数肯定是最大数，所以第二次就不需要遍历
                if (arr[j].compareTo(arr[j+1]) > 0)
                    swap(arr, j, j+1);
                else break;
            }
        }
    }

    /**
     * 优化排序
     * */
    public static void sort2(Comparable[] arr){
        int n = arr.length;
        int newn;
        do {
            newn = 0;
            for (int i = 1; i < n; i++){
                if (arr[i].compareTo(arr[i-1]) > 0){
                    swap(arr, i, i-1);
                    newn = i;
                }
            }
            n = newn;
        }while (newn>0);

    }

    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}
